package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/5/29 13:33
 * @description:
 */
public class ReConstructBinaryTree07 {
    public static void main(String[] args) {
        int [] preorder = {3,9,20,15,7};
        int [] inordder  = {9,3,15,20,7};
        TreeNode treeNode = new ReConstructBinaryTree07().ReConstructBinaryTree(preorder, inordder);
        System.out.println(treeNode);
    }
    //便利过程
    //建立根节点
    //前序遍历的每个可以确定该最小树的起始节点
    //中序以前序的节点为中轴，确定该前序节点在中序中的左节点与右节点
    //中止条件：

    public TreeNode ReConstructBinaryTree(int[] preorder, int[] inorder){
        if(preorder==null || inorder==null){
            return null;
        }

        return buildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    //根据前序和中序确定二叉树
    public  TreeNode buildTree(int[] preorder, int[] inorder, int pStart, int pend, int iStart, int iend){
        if(pStart>pend || iStart>iend){
            return null;
        }
        TreeNode root = new TreeNode(preorder[pStart]);
//        if(pStart==pend){
//            return root;
//        }
        int mid = iStart;
        while (mid<=iend && inorder[mid]!=root.val){
            mid++;
        }
        //找到mid即为根在中序中的位置
        int leftCount = mid - iStart;
        //重建左子树和右子树
        root.left=buildTree(preorder,inorder,pStart+1,pStart+leftCount,iStart,mid-1);
        root.right=buildTree(preorder,inorder,pStart+leftCount+1,pend,mid+1,iend);
        return root;
    }

    //根据后续和中序确定二叉树
    public TreeNode buildTree2(int[] inorder, int[] postorder, int iStart, int iend, int pStart, int pend){
        if(iStart>iend || pStart>pend){
            return null;
        }
        //构建新的root节点 /后续遍历序列的最后一个为根
        TreeNode root =new TreeNode(postorder[pend]);
        int mid=iStart;
        while(mid<=iend && inorder[mid]!=root.val){
            mid++;
        }
        int leftCount=mid-iStart;
        root.left=buildTree2(inorder, postorder, iStart, mid-1, pStart, pStart+leftCount-1);
        root.right=buildTree2(inorder,postorder,mid+1, iend, pStart+leftCount, pend-1);
        return root;
    }


}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}